Digital maps are found in a wide variety of devices, including car navigation systems, hand-held GPS units, mobile phones, and in many websites such as GOOGLE MAPS and MAPQUEST. Although digital maps are easy to use from an end-user's perspective, creating a digital map is a difficult and time-consuming process. Every digital map begins with a set of raw data corresponding to millions of streets and intersections. The raw map data is derived from a variety of sources, each source providing different amounts and types of information. In many cases, data from different sources is inaccurate and out of date. Oftentimes the data from the different sources are in a format that is not suitable for use in a real map. Integrating data from these heterogeneous sources so that it can be used and displayed properly is an enormous challenge.
In particular, raw map data often lacks information about turn restrictions. For cars that enter an intersection from a particular direction, turn restrictions provide information about the exits available from that intersection. Turn restrictions can be determined from road signs or lane markings. An example of a turn restriction is a sign at a four way intersection stating “no left turns.” Navigation devices need to know whether turns are restricted in order to generate a recommended driving route between two points on a map. Without this information, a navigation device is likely to provide erroneous driving instructions. For example, without turn restriction data, a navigation device may instruct a driver to make a U-turn at an intersection where U-turns are in-fact prohibited.